/*
You have given a dictionary and a string, you need to separate words that are in dictionary.
ex - catsanddog (here cat and cats both can be in dictionary)
output - cats and dog
*/

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

set<string> dict;

bool seperateWords(int index, const string &str, const set<string> &dict, vector<string> &cur, vector<vector<string> > &ans)
{
    if (index >=  str.size()) {
	ans.push_back(cur);
//	for (int i = 0; i < cur.size(); i++) 
//	    cout << cur[i] << " ";
//	cout << endl;
	return true;
    }

    for (int i = index; i < str.size(); i++) {
        string substr = str.substr(index, i - index +1);
        if (dict.count(substr))  {
	    //cout << substr << endl;
	    cur.push_back(substr);
            seperateWords(i+1, str, dict, cur, ans) ;
            cur.pop_back();
	}
    }
    return false;
}

int main(int argc, char **argv)
{
    dict.insert("cats");
    dict.insert("and");
    dict.insert("an");
    dict.insert("ddogs");
    dict.insert("ddog");
    dict.insert("s");
    dict.insert("dogs");
    dict.insert("cat");
    vector<vector<string> >ans;
    vector<string> cur;
    bool res = seperateWords(0, "catsanddogs", dict, cur, ans);
    cout << endl;
    for (int i = 0; i < ans.size(); i++) {
	for (int j = 0; j < ans[i].size(); j++) 
	    cout << ans[i][j] << " ";
	cout << endl;
    }
    cout << endl;
}
